package com.interview.javabasic.DataStructrue;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import sun.reflect.generics.tree.Tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = new TreeNode(1, "松江");
        TreeNode node2 = new TreeNode(2, "无用");
        TreeNode node3 = new TreeNode(3, "卢俊");
        TreeNode node4 = new TreeNode(4, "林冲");
        TreeNode node5 = new TreeNode(5, "离拧");

        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        binaryTree.setRoot(root);
        System.out.println("前序遍历：");
        binaryTree.preOrder();
        System.out.println("中序遍历：");
        binaryTree.infixOrder();
        System.out.println("后续遍历：");
        binaryTree.postOrder();

        //前序遍历查找测试
        TreeNode treeNode = binaryTree.preOrderSearch(2);
        if (treeNode!=null){
            System.out.println("扎到了，信息为no = "+treeNode.getNo()+"名字是："+treeNode.getName());
        }else {
            System.out.println("没有这个信息、");
        }


        //测试删除节点；
        System.out.println("删除前：");
        binaryTree.preOrder();
        binaryTree.deletNode(4);
        System.out.println("删除后：");
        binaryTree.preOrder();
    }
}

class TreeNode{
   private int no;
   private String name;
   private TreeNode left;
   private TreeNode right;
   public TreeNode(int no,String name){
       this.no = no;
       this.name = name;
   }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //编写节点前序遍历的方法
    public void preOrder(){
        System.out.println(this);//先输出父节点
        //递归向左子树的前序遍历
        if (this.left!=null){
            this.left.preOrder();
        }
        //递归向右子树
        if (this.right!=null){
            this.right.preOrder();
        }
    }




    //编写中序遍历的方法
    public void infixOrder(){
       if (this.left!=null){
           this.left.infixOrder();
       }
        System.out.println(this);
       if (this.right!=null){
           this.right.infixOrder();
       }
    }

    //编写后续遍历
    public void postOrder(){
       if (this.left!=null){
           this.left.postOrder();
       }
       if (this.right!=null){
           this.right.postOrder();
       }
        System.out.println(this);
    }

    //递归删除节点
    public void  deleteNode(int no){
        if (this.left!=null && this.left.no == no){
            this.left = null;
            return;
        }
        if (this.right!=null &&this.right.no == no){
            this.right=null;
            return;
        }
        if (this.left!=null){
            this.left.deleteNode(no);
        }
        if (this.right!=null){
            this.right.deleteNode(no);
        }
    }

    //前序遍历查找
    public TreeNode preOrderSearch(int no){
        System.out.println("进入了前序遍历查找");
       if (this.no == no){
           return this;
       }
       TreeNode resNode = null;
       if (this.left!=null){
           resNode = this.left.preOrderSearch(no);
       }
       if (resNode!=null){//左子树上面找到了
           return resNode;
       }
       if (this.right!=null){
           resNode = this.right.preOrderSearch(no);
       }
       return resNode;
    }

    //中序遍历查找
    public TreeNode infixOrderSearch(int no){
        System.out.println("进入了中序遍历查找");
      TreeNode resNode = null;
       if (this.left!=null){
           resNode = this.left.infixOrderSearch(no);
       }
       if (resNode!=null){
           return resNode;
       }
       if (this.no==no){
           return this;
       }
       if (this.right!=null){
           resNode = this.right.infixOrderSearch(no);
       }
       return resNode;
    }

    //后序遍历查找
    public TreeNode postOrderSearch(int no){
        System.out.println("进入了后序遍历查找");
       TreeNode resNode = null;
       if (this.left!=null){
           resNode = this.left.postOrderSearch(no);
       }
       if (resNode!=null){
           return resNode;
       }
       if (this.right!=null){
           resNode = this.right.postOrderSearch(no);
       }
       if (resNode != null){
           return resNode;
       }
       if (this.no == no){
           return this;
       }
       return null;

    }



}


class BinaryTree{
    private TreeNode root;

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //前序遍历
    public  void preOrder(){
        if (this.root!=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空！");
        }
    }
    //后序遍历
    public  void postOrder(){
        if (this.root!=null){
            this.root.postOrder();
        }else{
            System.out.println("二叉树为空！");
        }
    }
    //中序遍历
    public  void infixOrder(){
        if (this.root!=null){
            this.root.infixOrder();
        }else{
            System.out.println("二叉树为空！");
        }
    }

    //删除节点
    public void deletNode(int no){
        if (root != null){
            if (root.getNo()==no){
                root = null;
            }else{
                root.deleteNode(no);
            }
        }else {
            System.out.println("空树，无法删除！");
        }
    }

    //前序查找
    public TreeNode preOrderSearch(int no){
        if (root!=null){
            return root.preOrderSearch(no);
        }else {
            return null;
        }
    }

    //中序查找
    public TreeNode infixOrderSearch(int no){
        if (root!=null){
            return root.infixOrderSearch(no);
        }else{
            return null;
        }
    }

    //后序查找
    public TreeNode postOrderSearch(int no){
        if (root!=null){
            return root.postOrderSearch(no);
        }else{
            return null;
        }
    }


}